/* 497. 非重叠矩形中的随机点 */
/**
 * @param {number[][]} rects
 */
var Solution = function (rects) {
	this.arr = [0]
	this.rects = rects
	for (const rect of rects) {
		const a = rect[0],
			b = rect[1],
			x = rect[2],
			y = rect[3]
		/* 获取所有的点，如果有多个矩形，那么后面的矩形应该包含前面矩形中所有的点 */
		this.arr.push(this.arr[this.arr.length - 1] + (x - a + 1) * (y - b + 1))
	}
}
const binarySearch = (arr, target) => {
	let low = 0,
		high = arr.length - 1
	while (low <= high) {
		const mid = Math.floor((high - low) / 2) + low
		const num = arr[mid]
		if (num === target) {
			return mid
		} else if (num > target) {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return low
}
/**
 * @return {number[]}
 */
Solution.prototype.pick = function () {
	/* 在最后一个矩形包含的 点 中随机获取一个 点 */
	let k = Math.floor(Math.random() * this.arr[this.arr.length - 1])
	/* 
        找到矩形的编号
        random [0,n) 可能会返回0,arr[0]并不存在 
    */
	const rectIndex = binarySearch(this.arr, k + 1) - 1
	/* 找到随机值 k 在对应矩形中的编号 相对增量 */
	k -= this.arr[rectIndex]
	/* 获取左下角的值跟右上角的值 */
	const rect = this.rects[rectIndex]
	const a = rect[0],
		b = rect[1],
		y = rect[3]
	/* 还原索引 */
	const col = y - b + 1 /* 列上有多少个点,算上边框 */
	const da = Math.floor(k / col) /*  在a这个点的增量 */
	const db = k - col * da /* 剩下的是b的增量 */
	return [a + da, b + db] /* 在[a,b]点上增加增量返回 */
}
var solution = new Solution([
	[-2, -2, 1, 1],
	[2, 2, 4, 6],
])
console.log(solution.pick())
console.log(solution.pick())
console.log(solution.pick())
